The Dubins Traveling Salesman Problem (DTSP) has generated significantinterest over the last decade due to its occurrence in several civil andmilitary surveillance applications. Currently, there is no algorithm that canfind an optimal solution to the problem. In addition, relaxing the motionconstraints and solving the resulting Euclidean TSP (ETSP) provides the onlylower bound available for the problem. However, in many problem instances, thelower bound computed by solving the ETSP is far below the cost of the feasiblesolutions obtained by some well-known algorithms for the DTSP. This articleaddresses this fundamental issue and presents the first systematic procedurefor developing tight lower bounds for the DTSP.
展开▼
